//
//  CLOArithmeticLearnVC.swift
//  TestCode
//
//  Created by Clover on 2019/2/25.
//  Copyright © 2019 clover.com. All rights reserved.
//
// 算法学习 参考https://item.jd.com/12403068.html

import UIKit
protocol CLOArithmeticProtocol: class{
    func requiredFunc()
    func optionFunc()
}

extension CLOArithmeticProtocol{
    func optionFunc() {
        print("optionFunc")
    }
}

class CLOArithmeticLearnVC: UIViewController {
    weak var delegate: CLOArithmeticProtocol?
    
    override func viewDidLoad() {
        super.viewDidLoad()
        self.title = "算法"
        self.view.backgroundColor = #colorLiteral(red: 1.0, green: 1.0, blue: 1.0, alpha: 1.0)
        let all_arr = [22,129,19,9,1,2,1920,100];
//        let index = self.binarySearch(elements: [1,2,3,4,5,6,7,8,9,10], targer: 20)
//        let index = self.sort_maopao_arr(arr: arr)
         let option = self.majorityElement([1])
        print(option)
    }
}

//MARK: - Collection
extension CLOArithmeticLearnVC{
//  1. 2Sum问题 已知数组sums 是否求两个数之和target
//     let bool = self.towSum([1,2,3,4,5,6,7,8,9,10], 3)
    func towSum(_ nums:[Int], _ target: Int) -> Bool {
        var set = Set<Int>()
        for num in nums {
            if set.contains(target - num){
                return true
            }else{
                set.insert(num)
            }
        }
        return false
    }
    
//    2、 整形数组中，有且只有两个数之和等于目标值，求两个数在数组中的序号
    func onlyTowSum(_ nums: [Int], _ target: Int) -> [Int] {
        var numDic = [Int: Int]()
        for (index, num) in nums.enumerated() {
            if let lastIndex = numDic[target - num]{
                return [lastIndex,index]
            }else{
                numDic[num] = index
            }
        }
//        fatalError("error");
        return [];
    }
}

//MARK: - String


// search
extension CLOArithmeticLearnVC{
    // 二分法查找
//    1、原始版本
//    let index = self.binarySearch([1,2,3,4,5,6,7,8,9,10], 3)
    func binarySearch(elements: [Int], targer : Int) -> Int {
        var star = 0, end = elements.count - 1
       
        while star <= end {
            let mid = star + (end - star) / 2
            if elements[mid] == targer {
                return mid
            }else if elements[mid] < targer {
                star = mid + 1
            }else{
                end = mid - 1
            }
        }
        return -1
    }
 
    func sort_maopao_arr(arr: [Int]) -> [Int] {
        var newArr = arr
        for i in  0..<newArr.count{
            for j in 0..<newArr.count - 1 - i{
                print("-----")
                print(j)
                if newArr[j] > newArr[j + 1]{
                    let temp = newArr[j + 1]
                    newArr[j + 1] = newArr[j]
                    newArr[j] = temp
                    print(newArr)
                }
            }
        }
        return newArr
    }
    
    func majorityElement(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        if nums.count == 1{
            return nums.first!
        }
        var dic = Dictionary<String, Int>()
        let target = nums.count / 2
        for obj in nums {
            let str = String.init(format: "%d", obj)
            if (dic[str] != nil){
                dic[str] = dic[str]! + 1
                if dic[str]! > target{
                    return obj
                }
            }else{
                dic[str] = 1;
            }
        }
        return 0
    }
}

